// 是对直接插入排序的改进
// 又称为“缩小增量排序”
//


// Q
// 为啥shell sort分组之后就能提高效率？
// 对于奇数个的数组如何处理？按步长分组 ！所以此问题是不存在的？
//
//
#include <stdio.h>
#include "config.h"


int shell_sort(int arr[],int len)
{
	int tmp;
	int step;
	int i;
	int j;

	for(step = (len/2);step > 0;step /= 2)
	{
	
		for(i=step;i<len;i++)
		{
			tmp = arr[i];
			for(j=i;(j-step)>=0 && arr[j-step] > tmp;j -= step)
			{
				arr[j] = arr[j-step];
			
			}

			arr[j] = tmp;
		}
	}



     #if RESULT_PRINT
        int is_ascsending = 1;
	// print
        printf("%s\r\n",is_ascsending ? "ascending" : "descending");
        for(i = 0;i< len;i++)
        {
            printf("%d,",arr[i]);
        }
        printf("\r\n");
    #endif

	
	return 0;
}
